/**
	practical informatics exercise 1.3

	author: Sebastian Geschke
*/
#ifndef _TREE_H
#define _TREE_H

#include <cstdio>
#include <algorithm>

class Tree {
public:
	Tree() : root(0) { }
	
	virtual ~Tree() { 
		if (root){
			delete root;
			root = 0;
		} 
	}

	void insert(double d) {
		if (!root) root = new Node(d);
		else insert(root, d);
	}
	
	void print() const { print(root); }

	unsigned height() { return height(root); }

protected:

	struct Node {
		Node(double d) : data(d), left(0), right(0) { 
		}

		~Node() { 
			if (right) {
				delete right;
				right = 0;
			} 
			if (left) {
				delete left;
				left = 0;
			}
		}

		double data;
		Node *left, *right;
	};
	
	void print(Node *node) const {
		if (!node) return;
		print(node->left);
		printf("%.2f (%d)\n", node->data, height(node));
		print(node->right);
	}
	
	unsigned height(Node *node) const {
		if (!node) return 0;
		return 1 + std::max(height(node->left), height(node->right));
	}
	
	virtual void insert(Node* &node, double d) {
		if (!node) node = new Node(d);
		if (d < node->data)insert(node->left, d);
		else if (d > node->data) insert(node->right, d);
	}



	
	Node *root;
};

#endif /* _TREE_H */